We investigate monotone circuits with local oracles (K., 2016), i.e.,circuits containing additional inputs $y_i = y_i(\vec{x})$ that can performunstructured computations on the input string $\vec{x}$. Let $\mu \in [0,1]$ bethe locality of the circuit, a parameter that bounds the combined strength ofthe oracle functions $y_i(\vec{x})$, and $U_{n,k}, V_{n,k} \subseteq \{0,1\}^m$be the classical sets of positive and negative inputs considered for $k$-cliquein the approximation method (Razborov, 1985). Our results can be informallystated as follows. 1. For an appropriate extension of depth-$2$ monotone circuits with localoracles, we show that the size of the smallest circuits separating $U_{n,3}$(triangles) and $V_{n,3}$ (complete bipartite graphs) undergoes two phasetransitions according to $\mu$. 2. For $5 \leq k(n) \leq n^{1/4}$, arbitrary depth, and $\mu \leq 1/50$, weprove that the monotone circuit size complexity of separating the sets$U_{n,k}$ and $V_{n,k}$ is $n^{\Theta(\sqrt{k})}$, under a certain technicalassumption on the local oracle gates. The second result, which concerns monotone circuits with restricted oracles,extends and provides a matching upper bound for the exponential lower bounds onthe monotone circuit size complexity of $k$-clique obtained by Alon and Boppana(1987).
展开▼
机译：我们使用局部预言调查单调电路（K.，2016），即包含附加输入$ y_i = y_i（\ vec {x}）$的电路可以对输入字符串$ \ vec {x} $执行非结构化计算。令[\，0]中的$ \ mu \ in为电路的局部性，该参数限制了oracle函数$ y_i（\ vec {x}）$和$ U_ {n，k}，V_ { n，k} \ subseteq \ {0,1 \} ^ m $是在逼近方法中考虑$ k $ -clique的经典正负输入集（Razborov，1985）。我们的结果可以非正式地陈述如下。 1.对于使用localoracles对深度$ 2 $单调电路的适当扩展，我们显示了分隔$ U_ {n，3} $（三角形）和$ V_ {n，3} $的最小电路的大小（完整的二部图） ）根据$ \ mu $经历两个相变。 2.对于$ 5 \ leq k（n）\ leq n ^ {1/4} $，任意深度，和$ \ mu \ leq 1/50 $，我们证明了分离集合$ U_ {n的单调电路尺寸复杂性，k} $和$ V_ {n，k} $是$ n ^ {\ Theta（\ sqrt {k}）} $，在本地Oracle门上有一定的技术假设。第二个结果涉及具有有限预言的单调电路，扩展并为Alon和Boppana（1987）获得的$ k $ -clique单调电路尺寸复杂度的指数下限提供了一个匹配的上限。
展开▼
